package algorithms.leaning.class10;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 二叉树的非递归遍历
 *
 * @author guichang
 * @date 2021/6/8
 */

@SuppressWarnings("all")
public class Code3_二叉树_非递归遍历 {

    public static void main(String[] args) {
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7, 8, 9);
        // 先序遍历 [1, 2, 4, 8, 9, 5, 3, 6, 7]
        MyUtil.print(preTraversal(treeNode));
        // 后序遍历 [8, 9, 4, 5, 2, 6, 7, 3, 1]
        MyUtil.print(postTraversal(treeNode));
        // 中序遍历 [8, 4, 9, 2, 5, 1, 6, 3, 7]
        MyUtil.print(inTraversal(treeNode));
    }

    /**
     * 先序遍历非递归实现
     */
    public static List<Integer> preTraversal(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(curr.val);// 弹出头
            // 先右后左，这样出栈的顺序就是头左右了
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
        return list;
    }

    /**
     * 后序遍历非递归实现
     */
    public static List<Integer> postTraversal(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        // 要使用两个栈
        Deque<TreeNode> stack1 = new ArrayDeque<>();
        Deque<TreeNode> stack2 = new ArrayDeque<>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            TreeNode curr = stack1.pop(); // 头右左
            stack2.push(curr); // 头右左的方式入栈, 那么出栈的方式就是左右头了, 刚好是后序遍历
            if (curr.left != null) {
                stack1.push(curr.left);
            }
            if (curr.right != null) {
                stack1.push(curr.right);
            }
        }
        // 以左右头的方式出栈
        while (!stack2.isEmpty()) {
            list.add(stack2.pop().val);
        }

        return list;
    }

    /**
     * 中序遍历非递归实现
     */
    public static List<Integer> inTraversal(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = head;
        while (!stack.isEmpty() || curr != null) {
            // 当前节点不为null则压入栈, 继续找左孩子
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 当前节点为null则弹出后压右孩子入栈
            else {
                TreeNode node = stack.pop();
                list.add(node.val);
                curr = node.right;
            }
        }

        return list;
    }


}